package class02;

/**
 * 给定链表头节点，和一个值；
 * 要求：根据给定的值从小到大排序链表
 */
public class Code03_SmallerEqualBigger {
    static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }


    public static Node listPartition(Node head, int pivot) {
        // 1 申请6个变量
        Node sH = null; // small head
        Node sT = null; // small tail
        Node eH = null; // equal head
        Node eT = null; // equal tail
        Node mH = null; // big head
        Node mT = null; // big tail

        // 2 根据给定的值划分链表区间
        Node next;
        while (null != head) {
            // 此时断开当前值
            next = head.next;
            head.next = null;

            if (pivot > head.value) {
                //s
                if
                (null == sH) {
                    sH = head;
                    sT = head;
                } else {
                    sT.next = head;
                    sT = head;
                }
            } else if (pivot == head.value) {
                //e
                if (eH == null) {
                    eH = head;
                    eT = head;
                } else {
                    eT.next = head;
                    eT = head;
                }
            } else {
                //m
                if (mH == null) {
                    mH = head;
                    mT = head;
                } else {
                    mT.next = head;
                    mT = head;
                }
            }
            head = next;
        }

        // 3 将3个区间串联起来
        if (null != sT) {
            sT.next = eH;
            eT = eT == null ? sT : eT;
        }
        if (eT != null) { // 如果小于区域和等于区域，不是都没有
            eT.next = mH;
        }
        return sH != null ? sH : (eH != null ? eH : mH);
    }

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        Node head1 = new Node(7);
        head1.next = new Node(9);
        head1.next.next = new Node(1);
        head1.next.next.next = new Node(8);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(2);
        head1.next.next.next.next.next.next = new Node(5);
        printLinkedList(head1);

        head1 = listPartition(head1, 5);
        printLinkedList(head1);
    }
}
